package com.leetcode.offer;

import com.leetcode.entity.ListNode;

import java.util.List;
import java.util.Stack;

/**
 * @author zfl
 * @Classname ReverseList
 * @Description 反转链表
 * @Date 2020/10/21 16:00
 */
public class ReverseList {

    /**
     * @param head
     * @return
     * 执行用时：1 ms, 在所有 Java 提交中击败了8.52%的用户
     * 内存消耗：38.2 MB, 在所有 Java 提交中击败了96.52%的用户
     */
    public static ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        Stack<ListNode> stack = new Stack<>();
        ListNode pt = head;
        while (pt != null) {
            stack.add(pt);
            pt = pt.next;
        }
        head = stack.pop();
        pt = head;
        while (!stack.isEmpty()) {
            pt.next = stack.pop();
            pt = pt.next;
        }
        pt.next = null;
        return head;
    }

    /**
     * @param head
     * @return 双指针法
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：38.2 MB, 在所有 Java 提交中击败了95.44%的用户
     */
    public static ListNode reverseList2(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode pt = head;
        ListNode p1 = head;
        ListNode p2 = pt.next;
        pt = pt.next;
        p1.next = null;
        while (pt != null) {
            pt = pt.next;
            p2.next = p1;
            p1 = p2;
            p2 = pt;

        }
        return p1;
    }
}
